// https://www.lintcode.com/problem/sort-colors/my-submissions
// 三指针，快排
class Solution {
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
     
    // 使用一次扫描的办法。
    // 设立三根指针，left, index, right。定义如下规则：
    
    // left 的左侧都是 0（不含 left）
    // right 的右侧都是 2（不含 right）
    // index 从左到右扫描每个数，如果碰到 0 就丢给 left，碰到 2 就丢给 right。碰到 1 就跳过不管。
    void sortColors(vector<int> &nums) {
        if (nums.empty()) return;
        int left = 0, right = nums.size() - 1;
        int idx = 0;
        
// Input
// Show Difference
// [0,2,2,2,2,1,0,1,0,0,0,1,0,2,0]
// Output
// [0,0,0,0,0,0,1,1,1,0,2,2,2,2,2]
// Expected
// [0,0,0,0,0,0,0,1,1,1,2,2,2,2,2]
        // while (idx < right)
        while (idx <= right)
        {
            if (nums[idx] == 0)
            {
                swap(nums[idx], nums[left]);
                idx++; //不可能换来了2，因为前面遇到的2会进入下一个else
                left++;
            }
            else if (nums[idx] == 2)
            {
                swap(nums[idx], nums[right]);
                right--;
                // 可能换来了0，因为idx是从左往右的
            }
            else
                idx++;
        }
    }
};